package com.jxm.sort;

import java.util.Arrays;

/**
 * @Author: jxm
 * @Description: 选择排序api设计
 * @Date: 2022/6/9 10:23
 * @Version: 1.0
 */
public class Selection {

    /**
     * 原理：
     * 1.每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处
     * 的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引
     * 2.交换第一个索引处和最小值所在的索引处的值
     */

    /**
     * 对数组a元素进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        for(int i = 0;i<a.length - 1;i++){ //轮次
            //假定本次遍历，最小的值所在的索引是i
            int minIndex = i;
            for(int j = i+1;j< a.length;j++){ //比较次数，从第二开始比较
                if(greater(a[minIndex],a[j])){
                    //跟换最小值所在的索引
                    minIndex = j;
                }
            }
            //交换i索引处和minIndex索引处的值
            exch(a,i,minIndex);
        }
    }

    /**
     * 比较v元素是否大于w元素
     * @param v
     * @param w
     * @return
     */
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w) > 0;
    }

    /**
     * 数据元素 i 和 j 交换位置
     */
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    //最坏情况下：时间复杂度为O(N^2);
    public static void main(String[] args) {
        Integer[] array = {4,6,8,7,9,2,10,1};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}
